3370. Smallest Number With All Set Bits

Easy

題目描述

Description

You are given a positive number n.

Return the smallest number x greater than or equal to n, such that the binary representation of x contains only set bits

Example 1:

Input: n = 5
Output: 7
Explanation: The binary representation of 7 is "111".

Example 2:

Input: n = 10
Output: 15
Explanation: The binary representation of 15 is "1111".

Example 3:

Input: n = 3
Output: 3
Explanation: The binary representation of 3 is "11".

Constraints:

• 1 <= n <= 1000

解答

Solution

/**
 * @param {number} n
 * @return {number}
 */
var smallestNumber = function (n) {
  if (n > 511) return 1023;
  if (n > 255) return 511;
  if (n > 127) return 255;
  if (n > 63) return 127;
  if (n > 31) return 63;
  if (n > 15) return 31;
  if (n > 7) return 15;
  if (n > 3) return 7;
  if (n > 1) return 3;

  return 1;
};

解題思路

要找的是大於等於 n 的且全由 set bits 組成的數字

set bits 指的是在二進位表示法中的 1
而題目的範圍很小，為 1 <= n <= 1000
所以其實可以簡單列出所有小於等於 1000 且轉成二進位的全都由 1 組成的數字：

• 十進位的 1 轉成二進位是 1
• 十進位的 3 轉成二進位是 11
• 十進位的 7 轉成二進位是 111
• 十進位的 15 轉成二進位是 1111
• 十進位的 31 轉成二進位是 11111
• 十進位的 63 轉成二進位是 111111
• 十進位的 127 轉成二進位是 1111111
• 十進位的 255 轉成二進位是 11111111
• 十進位的 511 轉成二進位是 111111111

再大則是十進位的 1023 轉成二進位是 1111111111

所以程式可以寫成這樣，不管傳入 $1 \leq n \leq 1000$ 的任何一個數字都能判斷

var smallestNumber = function (n) {
  if (n > 511) return 1023; // 512 ~ 1000
  if (n > 255) return 511; // 256 ~ 511
  if (n > 127) return 255; // 128 ~ 255
  if (n > 63) return 127; // 64 ~ 127
  if (n > 31) return 63; // 32 ~ 63
  if (n > 15) return 31; // 16 ~ 31
  if (n > 7) return 15; // 8 ~ 15
  if (n > 3) return 7; // 4 ~ 7
  if (n > 1) return 3; // 2 ~ 3

  return 1; // 1
};

心得

酷酷的有點鑽漏洞